BOJ_11066_파일합치기

2차원 배열 DP(Dynamic Programming)을 이용해 파일을 합치는 최솟값을 구하는 문제

놓친 것

1. 문제에 "소설의 여러 장들이 연속이 되도록 파일을 합쳐나가고," 라는 대목이 있는데 문제를 세 번이나 읽었으면서 독해를 안 했다... 이것 때문에 접근 방법이 완전히 잘못됐었다. 문제를 더 꼼꼼하게 읽자!
2. n개를 합친 것 + 1개까지는 구상을 잘 했는데 n개를 합친 것 + m개를 합친 것을 어떻게 구해야 할지 가늠이 안 됐다. 풀이를 보니 삼중 반복문과 sum 배열을 활용해서 여러 장을 합친 값들을 비교했다.

package BJO;  
  
import java.io.BufferedReader;  
import java.io.IOException;  
import java.io.InputStreamReader;  
import java.util.stream.Stream;  
  
public class BJO_11066_파일합치기 {  
  
    static int K;  
    static int[] costArr;  
    static int[][] dp;  
    static int[] sum;  
  
    public static void main(String[] args) throws IOException {  
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));  
        int T = Integer.parseInt(br.readLine());  
        for (int i = 0; i < T; i++) {  
            K = Integer.parseInt(br.readLine());  
            costArr = Stream.of(br.readLine().split(" ")).mapToIntparseInt).toArray(;  
            dp = new int[K + 1][K + 1];  
            sum = new int[K + 1];  
  
          for (int j = 1; j <= K; j++) {  
             sum[j] = sum[j - 1] + costArr[j - 1];  
          }  
          combineChapter();  
       }  
    }  
  
    static void combineChapter() {  
        for (int i = 1; i <= K; i++) {  
            for (int j = 1; i + j <= K; j++) {  
                int end = i + j;  
                dp[j][end] = Integer.MAX_VALUE;  
  
                for (int k = j; k < end; k++) {  
                dp[j][end] = Math.min(dp[j][end], dp[j][k] + dp[k + 1][end] + sum[end] - sum[j - 1]);  
                }  
            }  
        }  
  
       System.out.println(dp[1][K]);  
    }  
}